package org.example.everyday;

import org.springframework.util.CollectionUtils;

import java.util.*;

/**
 * <p>
 * Description:TODO 详细描述
 * <p>
 * <p>
 *
 * @author anlu
 * @date 2022/5/23 0023 9:17
 */
public class Lc675 {
    int[][] dirs = {{-1,0},{1,0},{0,1},{0,-1}};
    public static void main(String[] args) {
        Lc675 lc675 = new Lc675();

        List<List<Integer>> list = new ArrayList<>();

        List<Integer> list1 = Arrays.asList(1,2,3);
        List<Integer> list2 = Arrays.asList(0,0,4);
        List<Integer> list3 = Arrays.asList(7,6,5);
        list.add(list1);
        list.add(list2);
        list.add(list3);

        int res = lc675.cutOffTree(list);
        System.out.println(res);

    }
    public int cutOffTree(List<List<Integer>> forest) {
        List<int[]> trees = new ArrayList<int[]>();
        int row = forest.size();
        int col = forest.get(0).size();
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if(forest.get(i).get(j) > 1){
                    trees.add(new int[]{i,j});
                }
            }
        }

        Collections.sort(trees,(a,b) -> forest.get(a[0]).get(a[1]) - forest.get(b[0]).get(b[1]));

        int cx = 0;
        int cy = 0;
        int ans = 0;
        for (int i = 0; i < trees.size(); i++) {
            int steps = bfs(forest,cx,cy,trees.get(i)[0],trees.get(i)[1]);
            if(steps == -1){
                return -1;
            }
            ans += steps;
            cx = trees.get(i)[0];
            cy = trees.get(i)[1];
        }
        return ans;
    }

    private int bfs(List<List<Integer>> forest, int sx, int sy, int tx, int ty) {
        if(sx == tx && sy == ty){
            return 0;
        }
        int row = forest.size();
        int col = forest.get(0).size();
        int step = 0;
        Queue<int[]> queue = new ArrayDeque<int[]>();
        boolean[][] visited = new boolean[row][col];
        queue.offer(new int[]{sx,sy});
        while (!queue.isEmpty()){
            step++;
            int sz = queue.size();
            for (int i = 0; i < sz; i++) {
                int[] cell = queue.poll();
                int cx = cell[0],cy = cell[1];
                for (int j = 0; j < 4; j++) {
                    int nx = cx + dirs[j][0];
                    int ny = cy + dirs[j][1];
                    if(nx >= 0 && nx < row && ny >= 0 && ny < col){
                        if(!visited[nx][ny] && forest.get(nx).get(ny) > 0){
                            if(nx == tx && ny == ty){
                                return step;
                            }
                            queue.offer(new int[]{nx,ny});
                            visited[nx][ny] = true;
                        }
                    }
                }
            }
        }
        return -1;
    }
}
